Here is the original image:

Edge detection can be used to remove the antialiasing. The netpbm package provides commands for edge detection. Here is the output of:

ppmtopgm fish-demo.ppm > fish-demo.pgm
pgmedge fish-demo.pgm > fish-demo-edge.pgm

If that edge image is turned into a black and white image using thresholding with:

pgmtopbm -threshold -value 0.1 fish-demo-edge.pgm > fish-demo-edge-0.1.pbm

Then it can used as a mask to remove the antialiasing pixels. In this case all the antialiasing can be replaced with black pixels. That is because all the edges in the image have black outlines. Simply using black for all the pixels will make the black lines become thicker than in the original image.
Here is how to do this:

• make a black image the same size as the original.
• then use the edge image as a mask to combine the black image with the original image.

  ppmmake black 400 162 > black_400x162.ppm
  pnmcomp -alpha fish-demo-edge-0.1.pbm black_400x162.ppm fish-demo.ppm > fish-demo-aliased.ppm
  

Here is the result. If you look closely it has no antialias.

Advanced antialiasing removal

If the image does not have black outlines around the colors, then simply replacing the antialiasing pixels with black will not work.
A better way is to find the closest neighboring pixel with a similar color to the antialiasing pixel.

Un - Weighted approach

A simple approach would be to look at a window of 8 (3^2 - 1), 24 (5^2 - 1), or 48(7^2 - 1) neighbors for each antialiasing pixel, make a list of all the colors of the non antialiasing neighboors and choose the closest one to color of the current pixel.

Potential problems with this approach

The problem with the un weighted approach is that there might be several colors within the window, and those colors might actually be "closer" to the antialiasing pixel. This would result in color speckles. To give an example look at what happens when the fish image is quantized with its actual palette:

original tooth	quantized tooth
	Notice the orange pixels in the tooth. This is because the closest color to the antialiasing pixels is orange.

In this particular case this wouldn't be a problem, because the orange area is so far away from the teeth. But you could imagine the orange area being within 5 pixels from the tooth and then this problem would ocur using the un-weighted technique.

Weighted approach

With a weighted approach both the color distance and the pixel distance would be taken into account. And each would be given a weight perhaps a non-linear weight. Therefore if the balck and yellow pixels of the tooth are closer than the orange pixels they would be given a higher score even if their colors were futher than the orange.

Clustering

In general it seems like a color clustering algorithm would beable to remove the antialiasing appropriately, without needing the edge detection. If a palette is given as input to this clustering algorithm it should be fine. The key part of this clustering algorithm is that is based on location and color. Most quantizing and posterizing algorithms only look at the color histogram and don't take into account the location of the pixel. Perhaps this one would work:
http://portal.acm.org/citation.cfm?id=89822.89823&dl=GUIDE&dl=GUIDE&CFID=1699523&CFTOKEN=96808052

fish-demo-edge-gray.png (image/png)
fish-demo-aliased.png (image/png)
fish-demo.png (image/png)
fish-tooth-scale_4.png (image/png)
fish-tooth-quant_palette-scale_4.png (image/png)